LOJ 10091 / BZOJ 1501 (Tarjan缩点)

Posted on | In , , ,

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 $ N $ 头牛，给你 $ M $ 对整数 $ (A,B) $，表示牛 $ A $ 认为牛 $ B $ 受欢迎。 这种关系是具有传递性的，如果 $ A $ 认为 $ B $ 受欢迎，$ B $ 认为 $ C $ 受欢迎，那么牛 $ A $ 也认为牛 $ C $ 受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
$(n\le 1000,m\le 5000)$

题目链接

题解

  • 求出强连通分量，缩点，然后判断是不是只有一个出度为零的点，如果是输出它的大小。
  • 错的板子耽误了我一下午

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

const int maxn = 10007;
const int maxm = 50007;

int head[maxn], nxt[maxm], to[maxm], tot;
int u[maxm], v[maxm];
int dfn[maxn], low[maxn], belong[maxn], scc, tms;
vector<int>dag[maxn];
stack<int>st;
bool vis[maxn], ins[maxn];
int n,  m;


void addedge(int u,int v)
{
    to[++tot]=v;
    nxt[tot]=head[u];
    head[u]=tot;
}

void tarjan(int u)
{
   dfn[u]=low[u]=++tms;
   st.push(u); ins[u]=1;
   for(int i=head[u]; i; i=nxt[i])
   {
       int v=to[i];
       if(!dfn[v])
       {
           tarjan(v);
           low[u]=min(low[u], low[v]);
       }
       else if(ins[v]){
        low[u]=min(low[u], dfn[v]);
       }
   }
   if(dfn[u] == low[u]){
      belong[u]=++scc;
      int y;
      do{
        y=st.top();
        st.pop();
        ins[y]=0;
        belong[y]=scc;
      }while(u!=y);
   }
}

int suodian()
{
    for(int i=1; i<=m; i++)
    {
        if(belong[u[i]] == belong[v[i]])
            continue;
        dag[belong[u[i]]].push_back(belong[v[i]]); //可能两个强联通之间有多条边
    }
    int cnt=0, id=0;
    for(int i=1; i<=scc; i++)
    {
        if(dag[i].size() == 0)
        {
            cnt++;
            for(int j=1; j<=n; j++){
                if(belong[j] == i)
                    id++;
            }
        }
    }
    if(cnt==1)
        return id;
    else
        return 0;
}

void solve()
{
    for(int i=1; i<=n; i++)
    {
        if(!dfn[i])
            tarjan(i);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &u[i], &v[i]);
        addedge(u[i], v[i]);
    }
    solve();
    printf("%d\n", suodian());
    return 0;
}